/* Copyright (c) 2006 by M Aamir Maniar 
 * 
 * Permission is hereby granted, free of charge, to any person obtaining 
 * a copy of this software and associated documentation files (the 
 * "Software"), to deal in the Software without restriction, including 
 * without limitation the rights to use, copy, modify, merge, publish, 
 * distribute, sublicense, and/or sell copies of the Software, and to 
 * permit persons to whom the Software is furnished to do so, subject to 
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be 
 * included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 * 
 * */

namespace Generic.Algorithms.Sorting
{

	using System;
	using System.Collections.Generic;
	using System.Text;
    using Generic.Utils;

	public class InsertionSortStrategy<T> : SortStrategy<T>
		where T : IComparable
    {

        #region public InsertionSortStrategy()
        /// <summary>
        /// Initializes a new instance of the <see cref="InsertionSortStrategy&lt;T&gt;"/> class.
        /// </summary>
        public InsertionSortStrategy()
        {
        }
        #endregion

        #region public InsertionSortStrategy(IList<T> list) : base(list)
        /// <summary>
		/// Initializes a new instance of the <see cref="GInsertionSortStrategy&lt;T&gt;"/> class.
		/// </summary>
		/// <param name="listToSort">The list to sort.</param>
		public InsertionSortStrategy(IList<T> list) : base(list)
		{
			List = list;
        }
        #endregion

        #region public override void Sort(SortDirection sortDirection)
        /// <summary>
        /// Sorts the list specified sort direction using applied sort strategy.
        /// </summary>
        /// <param name="sortDirection">The sort direction in which list to be sorted.</param>
        public override void Sort(SortDirection sortDirection)
		{
            base.Sort(sortDirection);

			bool descending = (sortDirection == SortDirection.Descending) ? true : false;
			int inner, outer;
            
            for (outer = 1; outer < List.Count; outer++)
			{
				T temp = List[outer];
				inner = outer;
				while (inner > 0 && (CompareTo(List[inner - 1],temp) > 0) ^ descending)
				{
					List[inner] = List[inner - 1];
					--inner;
				}
				List[inner] = temp;
			}
        }
        #endregion

    }
}
